//https://leetcode.cn/problems/swap-nodes-in-pairs/
package codeRandomThoughts.Test24两两交换链表中的节点;

import codeRandomThoughts.utils.ListNode;

public class Solution {
    /**
     * 迭代法
     *
     * @param head
     * @return
     */
    public ListNode swapPairs1(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return head;
        }
        //假头节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode curr = dummyHead;
        ListNode prev;
        ListNode next;
        while (true) {
            prev = curr;
            curr = curr.next;
            next = curr.next;
            //curr和next交换
            prev.next = next;
            curr.next = next.next;
            next.next = curr;
            if (curr.next == null || curr.next.next == null) {
                return dummyHead.next;
            }
        }
    }

    /**
     * 递归法
     * 简单明了,就是想不出来
     * @param head
     * @return
     */
    public ListNode swapPairs2(ListNode head) {
        if (head==null || head.next==null){
            return head;
        }
        ListNode one = head;
        ListNode two = one.next;
        ListNode three = two.next;
        two.next = one;
        one.next = swapPairs2(three);//把递归当当成结果来用

        return two;//头节点
    }
}
